package leetcode.weekly.week319;

import leetcode.helper.H;

//Solution4Test
class Solution6 {
	public int maxPalindromes(String s, int k) {
		int len = s.length();
		char[] cs = s.toCharArray();
		boolean[][] dp = new boolean[len][len];
		for (int i = 0; i < len; i++) {
			dp[i][i] = true;
		}
		for (int i = 0; i < len; i++) {
			for (int j = i; j >= 0; j--) {
				if (j == i)
					dp[j][i] = true;
				else if (j + 1 == i) {
					if (cs[i] == cs[j]) {
						dp[j][i] = true;
					}
				} else {
					if (cs[i] == cs[j] && dp[j + 1][i - 1]) {
						dp[j][i] = true;
					}
				}
			}
		}
		Integer[] dp2 = new Integer[len];//
		return this.f(cs, 0, dp2, dp, k);
	}

	private int f(char[] cs, int start, Integer[] dp2, boolean[][] dp, int k) {
		if (start == cs.length) {
			return 0;
		}
		if (dp2[start] != null) {
			return dp2[start];
		}
		int ans = this.f(cs, start + 1, dp2, dp, k);
		for (int j = start + k - 1; j < cs.length; j++) {
			if (dp[start][j]) {
				ans = Math.max(ans, 1 + this.f(cs, j + 1, dp2, dp, k));
			}
		}
		dp2[start] = ans;
		return ans;
	}
}
